iT邦幫忙

1

[LeetCode 筆記] 206. Reverse Linked List

  • 分享至 

  • xImage
  •  

前言

  這是一題單向鏈結串列反轉的題目,運用指標的算法,目標是將原本的鏈結串列倒序排列,此演算有使用到一個 while 迴圈,則時間複雜度估 O(n),這裡有 JAVA 和 Python 的寫法。

題目

Given the head of a singly linked list, reverse the list, and return the reversed list.

給定一個 head 單向鏈結串列,反轉這個串列,且回傳反轉過後的這個串列。

題目連結:https://leetcode.com/problems/reverse-linked-list/description/

題目限制

The number of nodes in the list is the range [0, 5000].
5000 <= Node.val <= 5000

範例

Reverse

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Reverse

Input: head = [1,2]
Output: [2,1]
Input: head = []
Output: []

思路&筆記

鏈結串列的題目,簡單想像是在處理節點的位置,資料先放一邊別去裡他。
這裡設定三個指標分別是指向 null 的 (指標一)、指向當前 head 的 (指標二)、輔助指標 nextNode (指標三)。

  • 設定好三個指標後
  • 把當前的 curr.next 掛在輔助指標 nextNode 上 (確保在反轉的過程中不會失去原始下一個節點的位置)
  • 掛完之後把當前節點 curr.next 指向 prev (此時指針已反轉了)
  • 接下來移動指針 prev 到 curr
  • 將 curr 掛在 nextNode (剛剛保存的原始下一個節點的位置)
  • 以上邏輯循環到最後,當 curr 移動到 null 時則停止迴圈 (鏈結串列的末端節點一定會指向 null)

[補充] curr.next 同等於 curr → link (指向下一個節點的意思)

JAVA 實現

class Solution {
    public ListNode reverseList(ListNode head) {

        ListNode curr = head; // 當前指標 (指標一)
        ListNode prev = null; // 空集合指標 (指標二)

        // 檢查確定鏈結串列裡有資料
        while (curr != null) {
            ListNode nextNode = curr.next; // 輔助指標 (指標三),指向下一個節點 (資料暫存在輔助指標內)
            curr.next = prev; // 將 curr 的 next 指針指向 prev,(將當前節點的指針方向反轉)
            prev = curr; // 更新指針指向:將 prev 設為 curr
            curr = nextNode; // curr 設為 nextNode
        }

        return prev;
    }
}

Python 實現

使用了和 Java 一樣的邏輯執行,換成 Python 的寫法。
(Python 中不需要再宣告一個額外的變數來存儲原始的鏈結串列)

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
			
        prev = None # 空集合指標 (指標一)

        while head:
            nextNode = head.next # 輔助指標 (指標二)
            head.next = prev # 反轉
            prev = head # 移動指標
            head = nextNode # 掛回去原本的鏈結串列

        return prev

成績

Language Runtime Memory
Java 0ms 41.8MB
Python 53ms 17.9MB

(新手上路,如有錯誤請友善告知,感謝)

Blog
https://chris81051.github.io/2023/06/29/LeetCode-206-Reverse-Linked-List-Java-Python/
有分享技術文章、科技新聞、日常生活,歡迎一起討論


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言